476. Number Complement

1. Question

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.

• For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.

Given an integer num, return its complement.

2. Examples

Example 1:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2:

Input: num = 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

3. Constraints

• 1 <= num < 2³¹

4. References

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/number-complement 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

5. Solutions

使用mask掩码解决前置0的问题

class Solution {
  public int findComplement(int num) {
    // 0按位取反，全1
    int mask = ~0;
    // 与运算，同1位1
    // 当结果不为0的时候，mask右移，直到结果为0
    // 此时mask类似于ip地址的子网掩码，与num相同进制上的数为0
    while ((mask & num) != 0) {
      mask <<= 1;
    }
    // 异或运算，不同为1，相同为0
    // 将num按位取反，并与mask异或去掉前半部分无效的1
    return ~num ^ mask;
  }
}